import copy
import math

import Commons


# 经过快速非支配排序和拥挤度计算得到的pareto前沿
def super(fitness):
    # 取编号、学生、老师为列表[[编号1,92,12051], [编号2,...], ......,[], [编号100,....]]
    schemas_fitness = Commons.numList(fitness)
    dominates = fast_non_dominated_sorting(schemas_fitness)
    paretofrontiers = paretoFrontier(dominates, schemas_fitness)
    new_paretofrontiers = congestionDistance(paretofrontiers)

    return new_paretofrontiers


# ----------------非支配排序--------------------------
# 快速非支配排序
# 计算np：种群中支配个体p的个体数，计算Sp：种群中被p支配的个体集合
# 记录所有方案的编号+学生+老师+支配它的个体数+被它支配的个体集合
# [[编号1, 183,450,156,17,20,...,1,6,4,2,...,92,12051],
# [编号2, 183,450,156,17,20,...,1,6,4,2,...,92,12051], [],.....[编号100,...]]
def fast_non_dominated_sorting(schemas_fitness):
    # 计算np和Sp，记录所有方案的编号+学生老师满意度+教室利用率+支配它的个体数+被它支配的个体集合
    dominates = []  # 记录所有排课方案的编号+学生教师样本方差+平均教室空闲数+支配它的个体数+被它支配的个体集合
    for numlist in schemas_fitness:  # numlist = [编号1,92,12051]
        num = 0  # 记录支配i个体的个体数
        dominated = []  # 存储被i支配个体的集合（编号）
        for l in schemas_fitness:  # l = [编号1,92,12051]
            # -------计算np----------
            if l[1] < numlist[1] and l[2] < numlist[2] and l[3] < numlist[3]:
                num += 1  # 计数器
            # -------计算Sp----------
            if l[1] > numlist[1] and l[2] > numlist[2] and l[3] > numlist[3]:
                dominated.append(l[0])  # 添加编号
        dominate = numlist.copy()  # 复制numlist列表，dominate = [编号1,92,12051]
        dominate.append(num)  # 保存支配i的个数
        dominate.append(dominated)  # 保存被i支配的集合
        dominates.append(dominate)
    # 结果形式：[[1,92,12051,67,[2,5,78]],[2,96,21035,3,[0,4,53,10]],...,[99,98,10000,0,[1]],[100,98,10000,0,[]]]
    return dominates


# 划分pareto前沿
# [[1,92,12051,67,[2,5,78]],[2,96,21035,3,[0,4,53,10]],...,[99,98,10000,0,[1]],[100,98,10000,0,[]]]
def paretoFrontier(dominates, schemas_fitness):
    paretofrontiers = []  # 保存所有pareto前沿
    # 遍历dominates，将每个点都划分到pareto前沿面
    while len(dominates) != 0:
        # 取n=0的个体，保存每个pareto前沿，结果：[[3,92,12051,0,[2,5,78]]...[51,92,12051,0,[4,53]],...,[99,92,12051,0,[1]],[100,92,12051,0,[]]]
        paretofrontier = []  # 保存rank1-pareto前沿
        for do in dominates:  # do = [1,92,12051,67,[2,5,78]]
            if do[4] == 0:
                paretofrontier.append(do)  # 将 n = 0 的点划入F1 ( 帕累托第一前沿)
        paretofrontiers.append(paretofrontier)  # 将每个前沿面保存到总列表中
        break
    return paretofrontiers  # 返回总列表


# 根据编号到numlists列表中查找对应个体的学生、老师，并存入newnumlists中
# def select_VSpace(dominates, numlists):
#     newnumlists = []  # 存储dominates中的经过上次快速非支配排序后所有个体编号+学生老师满意度+教室使用情况
#     # do = [1,92,12051,67,[2,5,78]]
#     for do in dominates:
#         newnumlist = []  # 存储dominates中的某个体编号+学生+老师
#         for i in range(len(numlists)):
#             if numlists[i][0] == do[0]:
#                 newnumlist = numlists[i]
#                 # 将找到的个体信息存入newnumlists列表中
#                 newnumlists.append(newnumlist)
#                 break
#     return newnumlists


# 拥挤度计算
def congestionDistance(paretofrontiers):
    copy_paretofrontiers = copy.deepcopy(paretofrontiers)
    newParetofrontiers = []  # 存储按照拥挤度排序后的个体列表
    for pareto in copy_paretofrontiers:  # 同一等级pareto前沿 = [ [3,95,12445,0,[2,5,78]], [51,94,1724,0,[4,53]],...,[99,98,1245,0,[]] ]
        newpareto = copy.deepcopy(pareto)  # 复制原始等级列表
        sortList = []
        if len(pareto) > 1:
            # 将同一等级的个体按某个目标函数的大小进行正向排序
            for i in range(1, 4):  # i = 1,2,3
                if i == 1:
                    # 将同一等级的个体按目标函数——学生教师满意度的大小进行正向排序
                    sortList = sorted(pareto, key=lambda x: x[1])
                    # [ [51,94,17240,0,[4,53]],[3,95,12445,0,[2,5,78]],...,[99,98,22405,0,[]] ]
                    minnum = sortList[0][1]  # 取最小值
                    maxnum = sortList[len(pareto) - 1][1]  # 取最大值
                    # 初始化同一等级中个体的拥挤距离为0
                    dis1 = [0 for i in range(len(pareto))]
                    # dis1[0] = float('inf')  # float('inf') 表示无穷大
                    # dis1[len(pareto) - 1] = float('inf')  # float('inf') 表示无穷大

                    if minnum != maxnum:
                        # spf 修改之前的拥挤度计算两端定义无穷大的问题，最大拥挤度一直在两个端点的问题-----------------------改进点
                        dis1[0] = float((sortList[1][1] - sortList[0][1]) * 2) / float(maxnum - minnum)  # 后面与之的距离乘以2
                        dis1[len(pareto) - 1] = float(
                            (sortList[len(sortList) - 1][1] - sortList[len(sortList) - 2][1]) * 2) / float(
                            maxnum - minnum)  # 前面与之距离乘2
                        if len(sortList) > 2:
                            # 计算其余个体的拥挤度
                            for j in range(1, len(pareto) - 1):
                                dis1[j] = float(sortList[j + 1][1] - sortList[j - 1][1]) / float(maxnum - minnum)
                    # 将每个个体的拥挤度添加到每个个体后
                    for k in range(len(sortList)):
                        sortList[k].append(dis1[k])
                        # 结果：# [ [51,94,17240,0,[4,53],0.4],[3,95,12445,0,[2,5,78],0.1],...,[99,98,22405,0,[],0.6] ]
                elif i == 2:
                    # 将同一等级的个体按目标函数——老师的大小进行正向排序
                    sortList = sorted(pareto, key=lambda x: x[2])
                    minnum = sortList[0][2]  # 取老师最小值
                    maxnum = sortList[len(sortList) - 1][2]  # 取老师最大值
                    # 初始化同一等级中个体的拥挤距离为0
                    dis2 = [0 for i in range(len(pareto))]
                    # dis2[0] = float('inf')  # float('inf') 表示无穷大
                    # dis2[len(pareto) - 1] = float('inf')  # float('inf') 表示无穷大

                    if minnum != maxnum:
                        dis2[0] = float((sortList[1][2] - sortList[0][2]) * 2) / float(maxnum - minnum)  # 后面与之的距离乘以2
                        dis2[len(pareto) - 1] = float(
                            (sortList[len(sortList) - 1][2] - sortList[len(sortList) - 2][2]) * 2) / float(
                            maxnum - minnum)  # 前面与之距离乘2
                        if len(sortList) > 2:
                            # 计算其余个体的拥挤度
                            for j in range(1, len(pareto) - 1):
                                dis2[j] = float(sortList[j + 1][2] - sortList[j - 1][2]) / float(maxnum - minnum)
                    # 计算每个个体的综合拥挤度替换到每个个体后
                    for k in range(len(sortList)):
                        # dis2[k] = dis2[k] + sortList[k][5]  # 计算综合拥挤度
                        # sortList[k][5] = dis2[k]  # 修改替换拥挤度
                        sortList[k].append(dis2[k])
                        # 结果：# [ [51,94,17240,0,[4,53],1.0],[3,95,12445,0,[2,5,78],0.5],...,[99,98,22405,0,[],1.3] ]
                elif i == 3:
                    # 将同一等级的个体按目标函数——老师的大小进行正向排序
                    sortList = sorted(pareto, key=lambda x: x[3])
                    minnum = sortList[0][3]  # 取老师最小值
                    maxnum = sortList[len(sortList) - 1][3]  # 取老师最大值
                    # 初始化同一等级中个体的拥挤距离为0
                    dis3 = [0 for i in range(len(pareto))]
                    # dis2[0] = float('inf')  # float('inf') 表示无穷大
                    # dis2[len(pareto) - 1] = float('inf')  # float('inf') 表示无穷大

                    if minnum != maxnum:
                        dis3[0] = float((sortList[1][3] - sortList[0][3]) * 2) / float(maxnum - minnum)  # 后面与之的距离乘以2
                        dis3[len(pareto) - 1] = float(
                            (sortList[len(sortList) - 1][3] - sortList[len(sortList) - 2][3]) * 2) / float(
                            maxnum - minnum)  # 前面与之距离乘2
                        if len(sortList) > 2:
                            # 计算其余个体的拥挤度
                            for j in range(1, len(pareto) - 1):
                                dis3[j] = float(sortList[j + 1][3] - sortList[j - 1][3]) / float(maxnum - minnum)
                    # 计算每个个体的综合拥挤度替换到每个个体后
                    for k in range(len(sortList)):
                        dis3[k] = math.sqrt(
                            pow(dis3[k], 2) + pow(sortList[k][6], 2) + pow(sortList[k][7], 2))  # 计算综合拥挤度
                        sortList[k][6:8] = [dis3[k]]  # 修改替换拥挤度
                        # 结果：# [ [51,94,17240,0,[4,53],1.0],[3,95,12445,0,[2,5,78],0.5],...,[99,98,22405,0,[],1.3] ]
            # 其中5就代表按照第六列数据进行倒序排序
            newpareto = sorted(sortList, key=lambda x: -x[6])
        else:
            # 若等级中只有一个个体，设它的拥挤距离为0
            newpareto[0].append(0)
        # 将每一等级排序好的个体列表存入总列表中
        newParetofrontiers.append(newpareto)
    return newParetofrontiers
